# 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。


# 方法1：非递归方法
def Convert(pRootOfTree):
    if not pRootOfTree:
        return None
    p = pRootOfTree  # 这些都是引用，不算创建新的节点
    stack = []
    resultStack = []
    root = None
    while p or stack:
        if p:
            stack.append(p)
            p = p.left  # 这会一直走到左子树的最后一个左边叶子节点
        else:
            temp = stack.pop()  # 然后，再从后往前一个一个的弹出来，最先弹出来的当然是最左边的节点
            resultStack.append(temp)  # 加进来，这里其实隐含了左和根的加入
            p = temp.right  # 最后，右节点
    root = resultStack[0]  # 保留头节点
    while resultStack:
        temp = resultStack.pop(0)
        if resultStack:
            temp.right = resultStack[0]  # 【node2，←node1→，node3】，最初是这样的结构，现在要做成双向的，也就是【node2→，←node1→，←node3】这样的
            resultStack[0].left = temp
    return root


# 方法2，递归
def Convert1(pRootOfTree):
    if not pRootOfTree:
        return None
    if not pRootOfTree.left and not pRootOfTree.right:
        return pRootOfTree
    # 将左子树构建成双链表，返回链表头
    left = Convert1(pRootOfTree.left)
    p = left
    #     定位至左子树最后一个节点
    while left and p.right:
        p = p.right

    #   如果左子树不为空，将当前root加到链表最后一个节点上
    if left:
        p.right = pRootOfTree
        pRootOfTree.left = p
    # 将右子树构建成双链表，返回链表头
    right = Convert1(pRootOfTree.right)
    # 如果右子树不为空，将该链表加到root之后
    if right:
        pRootOfTree.right = right
        right.left = pRootOfTree

    return left if left else pRootOfTree


li = [1, 2, 3]
print(li.pop())  # 默认会把最后一个pop出来
